#include<assert.h>
#include<iostream>
#include<math.h>

namespace xzj
{
    template<class K>
    struct AVLTreeNode
    {
        AVLTreeNode(const K& key)
            : _parent(nullptr)
            , _left(nullptr)
            , _right(nullptr)
            , _key(key)
            , _bf(0)
        {}

        AVLTreeNode* _parent;
        AVLTreeNode* _left;
        AVLTreeNode* _right;
        K _key;
        int _bf;
    };

    template<class K>
    class AVLTree
    {
        typedef AVLTreeNode<K> Node;
    public:
        AVLTree()=default;

        bool insert(const K& key)
        {
            if(_root==nullptr)
            {
                _root = new Node(key);
                return true;
            }

            Node* cur = _root;
            Node* parent = nullptr;
            while(cur)
            {
                if(cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else if(cur->_key<key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else 
                {
                    return false;
                }
            }

            cur = new Node(key);
            if(parent->_key>key)
            {
                parent->_left = cur;
                parent->_bf--;
            }
            else 
            {
                parent->_right = cur;
                parent->_bf++;
            }
            cur->_parent = parent;

                while(parent&&(parent->_bf==-1||parent->_bf==1))
                {
                    Node* grandparent = parent->_parent;
                    if(grandparent)
                    {

                        if(grandparent->_left==parent)
                        {
                            grandparent->_bf--;
                        }
                        else 
                        {
                            grandparent->_bf++;
                        }
                    }

                    cur = parent;
                    parent = grandparent;
                }

                if(parent==nullptr||parent->_bf==0)
                    return true;

                if(parent->_bf==-2&&cur->_bf==-1)
                {
                    RotateR(parent);
                }
                else if(parent->_bf==-2&&cur->_bf==1)
                {
                    RotateLR(parent);
                }
                else if(parent->_bf==2&&cur->_bf==1)
                {
                    RotateL(parent);
                }
                else if(parent->_bf==2&&cur->_bf==-1)
                {
                    RotateRL(parent);
                }
                else 
                {
                    assert(false);
                }

 
            return true;
        }

        void InOrder()
        {
            _Inorder(_root);
            std::cout<<std::endl;
        }

        bool IsBalanceTree()
		{
			return _IsBalanceTree(_root);
		}

		int height()
		{
			return _Height(_root);
		}


    private:
        void _Inorder(Node* root)
        {
            if(root==nullptr)
                return;

            _Inorder(root->_left);
            std::cout<<root->_key<<" ";
            _Inorder(root->_right);
        }

        void RotateL(Node* parent)
        {
            Node* subR = parent->_right;
            Node* subRL = subR->_left;
            if(subRL)
                subRL->_parent = parent;

            parent->_right = subRL;
            subR->_left = parent;
            if(parent->_parent==nullptr)
            {
                _root = subR;
            }
            else 
            {
                if(parent->_parent->_left == parent)
                {
                    parent->_parent->_left = subR;
                }
                else 
                {
                    parent->_parent->_right = subR;
                }
            }

            subR->_parent = parent->_parent;
            parent->_parent = subR;
            subR->_bf=0;
            parent->_bf=0;
        }

        void RotateR(Node* parent)
        {
            Node* subL = parent->_left;
            Node* subLR = subL->_right;
            if(subLR)
                subLR->_parent = parent;

            parent->_left = subLR;
            subL->_right = parent;

            if(parent->_parent==nullptr)
            {
                _root = subL;
            }
            else 
            {
                if(parent->_parent->_left == parent)
                {
                    parent->_parent->_left = subL;
                }
                else 
                {
                    parent->_parent->_right = subL;
                }
            }

            subL->_parent = parent->_parent;
            parent->_parent = subL;
            subL->_bf = 0;
            parent->_bf = 0;
        }

        void RotateLR(Node* parent)
        {
            Node* subL = parent->_left;
            Node* subLR = subL->_right;
            int bf = subLR->_bf;
            RotateL(subL);
            RotateR(parent);

            if(bf==0)
            {
                subL->_bf = 0;
                parent->_bf = 0;
                subLR->_bf = 0;
            }
            else if(bf==-1)
            {
                subL->_bf = 0;
                parent->_bf = 1;
                subLR->_bf = 0;
            }
            else 
            {
                subL->_bf = -1;
                parent->_bf = 0;
                subLR->_bf = 0;
            }
        }

        void RotateRL(Node* parent)
        {
            Node* subR = parent->_right;
            Node* subRL = subR->_left;
            int bf = subRL->_bf;

            RotateR(subR);
            RotateL(parent);

            if(bf==0)
            {
                subR->_bf = 0;
                parent->_bf = 0;
                subRL->_bf = 0;
            }
            else if(bf==-1)
            {
                subR->_bf = 1;
                parent->_bf = 0;
                subRL->_bf = 0;
            }
            else 
            {
                subR->_bf = 0;
                parent->_bf = -1;
                subRL->_bf = 0;
            }
        }

        int _Height(Node* root)
		{
			if (root == nullptr)
				return 0;

			int leftHeight = _Height(root->_left);
			int rightHeight = _Height(root->_right);
			return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
		}

		bool _IsBalanceTree(Node* root)
		{
			// 空树也是AVL树
			if (nullptr == root)
				return true;
			// 计算pRoot结点的平衡因?：即pRoot左右?树的?度差
			int leftHeight = _Height(root->_left);
			int rightHeight = _Height(root->_right);
			int diff = rightHeight - leftHeight;
			// 如果计算出的平衡因?与pRoot的平衡因?不相等，或者
			// pRoot平衡因?的绝对值超过1，则?定不是AVL树
			//KeyOfT kot;
			if (abs(diff) >= 2)
			{
                std::cout << root->_key << "?度差异常" << std::endl;
				return false;
			}
			if (root->_bf != diff)
			{
                std::cout << root->_key<< "平衡因?异常" << std::endl;
				return false;
			}
			// pRoot的左和右如果都是AVL树，则该树?定是AVL树
			return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
		} 

        Node* _root=nullptr;
    };
}
